#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10

void max_heapify(int* A, int i){
  int l = 2 * i;
  int r = 2 * i + 1;
  int largest;

  if( l <= N && A[l] > A[i] ){
    largest = l;
  } else{
    largest = i;
  }

  if( r <= N && A[r] > A[largest]){
    largest = r;
  }

  if(largest != i){
    int temp = A[i];
    A[i] = A[largest];
    A[largest] = temp;
    max_heapify(A, largest);
  }
}

int main(){

  int* A = (int*) malloc(N * sizeof(int));
  int i;
  clock_t t1, t2;
  A = A - 1;
  A[1] = 16; 
  A[2] = 4;
  A[3] = 10;
  A[4] = 14;
  A[5] = 7;
  A[6] = 9;
  A[7] = 3;
  A[8] = 2;
  A[9] = 8;
  A[10] = 1;

  t1 = clock();
  max_heapify(A, 2);
  t2 = clock();
  printf("tempo de execução %g\n", (t2-t1) / CLOCKS_PER_SEC);
  
  for(i=1; i <= N; i++){
    printf("%d -> %d\n", i, A[i]);
  }

  A = A + 1;
  free(A);
}
